package 动态规划;

public class leetcode1014最佳观光组合 {
/**
 * 这道题 就不是用  动态 规划的  优化  题目 
 * 动态 规划 根本 就无法 优化     这道题 目 
 * 
 * 
 * 这 用贪心 来解释 更合理 
 * values [i] +i + values[j] -j （ i <    j ）的最大值
 * 你认为 在 0 - len 中 找到 一个 values[i] + i 最大  再找 到 values[j] -j 的最大
 * 那么两者相加 就是最大                 这是 确实 是 局部 最大 --> 全局最大    但是 忽略 一个 重要 问题 是 i < j   
 * 所以 这种想法 	  是错的   所以 要控制 i< j 前提 下 去  寻找 那 两个 最大  
 * 这就是贪心问题  
 * 说白了 就是 啥 啊 
 * 在 
 */
  public static int greedy(int values[]) {
	  int maxScore = Integer.MIN_VALUE;
	//  int leftValue = values[0] + 0;  // 明白 这是 什么意思吧
	  int leftValue = Integer.MIN_VALUE;
	  for(int j = 1 ;j < values.length; j++) {
		  leftValue = Math.max(values[j-1] + j-1, leftValue);
		  maxScore = Math.max(maxScore, values[j] - j +leftValue);
//		  leftValue = Math.max(values[j] + j, leftValue);
	  }
	  return maxScore;
  }
  
/**
 * 这种 他妈 的 是错的 我靠 
 * 服了 
 * 还是 那个问题 
 * 按照 下面 这种   写法  
 * 还是    会 存在  i > j 的情况 结果 
 * 那不就错了 
 * [2,2,2]  values[i] +i最大 是 index 为 2时候 
 * 但是  values[j] - j最大 是在 index  为 1 的时候 
 * 那这   不就错了 对吧   
 * 这就是 贪心问题 
 * @param values
 * @return
 */
public static int greedy1(int values[]) {
	int maxJ = Integer.MIN_VALUE;
	int maxI = maxJ;
	for(int j = 1;j < values.length;j++ ) {
		maxJ = Math.max(maxJ, values[j] - j);
		maxI = Math.max(maxI, values[j - 1] + j -1);
	}
	return maxJ + maxI;
}
	
	
//*************************************************************************************
	
	

	
	
/**
 *暴力递归 
 *
 *这么 神奇的 嘛 这个过程 我靠 
 *这个 过程 真的 是太美妙了 说实话
 * @param values
 * @param index
 * @return
 * 但是 这里面 又有一个问题 就是
 * 没有 basecase 
 * 怎么 去初始化 这个 dp 数组的 初始化 值 
 * 如果 dp 数组 没有  初始化 的 值 话 默认 全都是 0 那么 0 就是 初始化 值？？ 
 */
	public static int solution(int values [],int index) {
//		basecase  
//		if() {
//			
//		}
		int score = 0;
		for(int i = index +1; i < values.length  ;i++) {
			  int score1 = values[index] +values[i] + index - i; 
//			  score = Math.max(score1, solution(values,i));
			  score = Math.max(score,Math.max(score1, solution(values,i)));
		}
		return score;
	}
	/**
	 * 这个 dp  虽然 能过 但是 我自己 都不明白 这 个 方法 是  怎么做到的 我 靠
	 * 依然 超时 
	 * @param values
	 * @return
	 * 这有一个 问题 在这里 为啥  递归 改了 动态 规划 之后 为啥 还超时 了 
	 * 因为 这 个 题 的过程 就没有 重复 的  子过程 
	 * 所以 即使 改成  动态 规划 复杂度 也没有 任何 改变 
	 * 跟 暴力for  循环的 是一样的 时间复杂度 的结果 
	 */
	public static int dp1(int values[]) {
		int len = values.length;
		int dp [] = new int [len];
		for(int index = len -1;index >=0; index--) {
			int score = 0;
			for(int i = index+1; i < len ;i++) {
				int score1 = values[index] + values[i]+ index - i;
				score = Math.max(score, Math.max(score1, dp[i]));
			}
			dp[index] = score;
		}
		return dp[0];
	}
/**
 *  暴力 for 循环 写
 *  这种 连想 都不用 肯定超时 的 
 *  目的 就是让你用 动态规划的
 *  但是 暴力 for 循环 不好 改成 动态规划的 
 *  所以 才要写 暴力 递归 
 *  
 *  别
 *  是暴力 for循环 你不会改 dp
 *  还是 暴力for 不能改 dp
 *  这是 两码事 对吧
 */
  public static int solution(int values []) {
	  int maxScore = 0;
	  int len = values.length;
	  int temp = 0;
	  for(int i = 0; i< len; i++) {
		  for(int j = i+1 ;j < len;j++) {
			  temp = values[i] + values[j] + i - j;
			  if(maxScore < temp) {
				  maxScore  = temp;
			  }
		  }
	  }
	  return maxScore;
  }
	
  
  	public static void main(String []args) {
//  		int []values = {8,1,5,2,6};
//  		int values []= {1,2};
  		   int values [] = {2,2,2};
  		System.out.println(solution(values));
  		System.out.println(solution(values,0));
  		System.out.println(dp1(values));
  		System.out.println(greedy(values));
  		System.out.println(greedy1(values));
  	}
  
}
